1. Field of the Invention
The invention relates to a field-programmable gate array which can be defined or redefined functions by a user.
2. Description of the Related Art
A field-programmable gate array has a plurality of logic elements and is designed to obtain desirable logic functions by interconnecting the adjacent logic elements (e.g., see Frederick Furtek et al., "LABYRINTH: A Homogeneous Computational Medium", IEEE 1990 Custom Integrated Circuits Conference Proceedings, pp. 31.1.1-31.1.4, 1990; and Tapio Korpiharju et al., "TUTCA configurable logic cell array architecture", 1991 IEEE International ASIC Conference Proceedings, P3-3.1-P3-3.4, 1991).
Conventionally, when only "local" signal lines are used for the interconnection of logic elements of a field-programmable gate array, it is difficult to interconnect logic elements that are remote from each other (are not adjacent each other). Therefore, interconnection using only the "local" signal lines is considered inflexible. The term "local" is herein construed as specifying a signal line used to interconnect logic elements closest to each other. The feature of the "local" signal line is a smaller load capacity and line delay than other "global" signal lines (e.g., a clock signal line) and signal lines directlyinterconnecting logic elements that are remote each other.
FIG. 8 shows a way of interconnecting "local" signal lines which is common in the conventional field-programmable gate arrays disclosed in the above-mentioned two technical documents.
In FIG. 8, reference numeral 50 designates a logic element. FIG. 9 is a diagram showing an internal architecture of the logic element. The logic element 50 receives signals 51-a, 51-b, 51-c, 51-d from the four logic elements that are adjacent thereto up, down, right, and left, through signal lines, respectively, and outputs signals 53-a, 53-b, 53-c, 53-d through signal lines, respectively. As shown in FIG. 9, the logic element 50 includes four circuits 52-a, 52-b, 52-c, 52-d. The respective circuits 52-a, 52-b, 52-c, 52-d receive the four signals 51-a, 51-b, 51-c, 51-d applied to the logic element 50 and outputs the upward signal 53-a, the downward signal 53-b, the leftward signal 53-c, and the rightward signal 53-d.
The case of forming a weighted mean circuit and an adder will be described as the example of forming various circuits using the above-mentioned field-programmable gate array.
FIG. 10 shows a weighted mean circuit; and FIG. 11 shows an adder. In FIGS. 10 and 11, reference numeral 100 designates a delay circuit; 101, an adder; 102, a divider; 103, a full adder; and 104, a half adder.
As is apparent from FIG. 10, the signal flow in which two inputs to each adder 101 enter from a single side and exit to a side opposite to such single side is reasonable in terms of the physical arrangement of the circuit and the principle of pipelining, and is therefore quite natural.
It is presumed to form an n-bit adder Using the conventional field-programmable gate array shown in FIG. 8. Here, each logic element has a function of a 1-bit full adder.
FIG. 12 shows interconnections for a single bit(surrounded by broken line) in the case of forming an n-bit adder by using the conventional field-programmable gate array. In FIG. 12, reference characters 50-a, 50-b, 50-c, 50-d designate logic elements, respectively; and 55, a partial circuit for a single bit of the n-bit adder. The logic elements 50-a and 50-b store inputs A.sub.i, B.sub.i, respectively, and outputs these signals rightward. The logic element 50-c outputs an input from left directly downward and an input from below (carry-out signal CO.sub.i) directly upward. The logic element 50-d receives an input A.sub.i from above, an input B.sub.i from left, and an input CI.sub.i from below, adds these signals up, and outputs the sum S.sub.i rightward and the carry-out signal CO.sub.i upward.
In the thus described architecture, the n-bit adder requires 4.times.n logic elements. The same applies to bit parallel logic operation units, with an n-bit logic operation unit requiring 4.times.n logic elements.
The problem encountered when such n-bit adder or logic operation unit is formed using the conventional field-programmable gate array is a low utilization of the logic elements.